SuperHack/SuperHack CD.bin/CODING/CPP/BTREE.ZIP/BNODE.H

C/C++ Source or Header | 1994-11-14 | 8.1 KB | 427 lines

/*
 *  BNode.h            Balanced Node Class
 *
 * (c) DownEast Technology, Inc., 1994
 * Written by Steve Nutt
 */

#if !defined(BNODE_H)
#define BNODE_H

#if !defined(__CLASSLIB_STACKS_H)
#include <ClassLib\Stacks.h>
#endif

enum TBalance {
    LeftBalance                = -1,
    Balanced                    = 0,
    RightBalance            = 1,
    DoubleLeftBalance        = LeftBalance * 2,
    DoubleRightBalance    = RightBalance * 2,
};

/*
 * Template TNodeImp
 * Contains common functionality to manage traversing and balancing nodes.
 */
template <class Alloc> class TNodeImp : public Alloc
{
public:
    typedef TNodeImp TNodeBase;
    typedef TIStackAsVector<TNodeBase*> TChain;

    TNodeImp (void) : balance (Balanced)
        {
        left = right = 0;
        }

    TNodeImp*& Left (void)
        {
        return left;
        }

    TNodeImp*& Right (void)
        {
        return right;
        }

    TNodeImp& LeftNode (void) const
        {
        PRECONDITION (left);
        return *left;
        }

    TNodeImp& RightNode (void) const
        {
        PRECONDITION (right);
        return *right;
        }

    BOOL BalanceAdd (TNodeImp* child, TNodeImp*& head)
        {
        balance = static_cast<TBalance> (balance + ((child == left) ?
            LeftBalance : RightBalance));
        return Balance (head);
        }

    BOOL BalanceDetach (TNodeImp* child, TNodeImp*& head)
        {
        balance = static_cast<TBalance> (balance + ((child == right) ?
            LeftBalance : RightBalance));
        return Balance (head);
        }

    TBalance& Balance (void)
        {
        return balance;
        }

    TNodeImp* WalkLeft (void);
    TNodeImp* WalkRight (void);
    TNodeImp* WalkLeft (TChain&);
    TNodeImp* WalkRight (TChain&);
    void RotateLeft (TNodeImp*&);
    void RotateRight (TNodeImp*&);
    void RotateLeftRight (TNodeImp*&);
    void RotateRightLeft (TNodeImp*&);
    BOOL Balance (TNodeImp*&);
    static TNodeImp* Next (TChain&);
    static TNodeImp* Previous (TChain&);

#if __DEBUG > 0
#if defined(_DEBUG_B_TREE_)
    unsigned CheckNode (int&);
#endif
#endif

private:
    TNodeImp* left;
    TNodeImp* right;
    TBalance balance;

    const TNodeImp& operator = (const TNodeImp& other);
    TNodeImp (const TNodeImp&);
};

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::Next (
    TChain& chain)
{
    const TNodeImp* child = 0;
    while (!chain.IsEmpty())
    {
        TNodeImp& node = **chain.Top();
        if (child && node.Left() == child)
            return &node;

        if (node.Right() && node.Right() != child)
        {
            chain.Push (&node.Right());
            return node.RightNode().WalkLeft (chain);
        }
        child = &node;
        chain.Pop();
    }
    return 0;
}

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::Previous (
    TChain& chain)
{
    const TNodeImp* child = 0;
    while (!chain.IsEmpty())
    {
        TNodeImp& node = **chain.Top();
        if (child && node.Right() == child)
            return &node;

        if (node.Left() && node.Left() != child)
        {
            chain.Push (&node.Left());
            return node.LeftNode().WalkRight (chain);
        }
        child = &node;
        chain.Pop();
    }
    return 0;
}

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::WalkLeft (void)
{
    TNodeImp* node = this;
    while (node->left)
        node = node->left;

    return node;
}

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::WalkRight (void)
{
    TNodeImp* node = this;
    while (node->right)
        node = node->right;

    return node;
}

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::WalkLeft (
    TChain& chain)
{
    TNodeImp* node = this;
    while (node->left)
    {
        chain.Push (&node->left);
        node = node->left;
    }
    return node;
}

template <class Alloc>
TNodeImp<Alloc>* TNodeImp<Alloc>::WalkRight (
    TChain& chain)
{
    TNodeImp* node = this;
    while (node->right)
    {
        chain.Push (&node->right);
        node = node->right;
    }
    return node;
}

template <class Alloc>
void TNodeImp<Alloc>::RotateLeft (
    TNodeImp*& head)
{
    PRECONDITION (balance == DoubleRightBalance);
    TNodeImp& child = RightNode();
    PRECONDITION (child.balance != LeftBalance);
    right = child.left;
    child.left = this;
    head = &child;
    if (child.balance == RightBalance)
        balance = child.balance = Balanced;
    else    // child.balance == Balanced
    {
        balance = RightBalance;
        child.balance = LeftBalance;
    }
}

template <class Alloc>
void TNodeImp<Alloc>::RotateRight (
    TNodeImp*& head)
{
    PRECONDITION (balance == DoubleLeftBalance);
    TNodeImp& child = LeftNode();
    PRECONDITION (child.balance != RightBalance);
    left = child.right;
    child.right = this;
    head = &child;
    if (child.balance == LeftBalance)
        balance = child.balance = Balanced;
    else    // child.balance == Balanced
    {
        balance = LeftBalance;
        child.balance = RightBalance;
    }
}

template <class Alloc>
void TNodeImp<Alloc>::RotateLeftRight (
    TNodeImp*& head)
{
    PRECONDITION (balance == DoubleLeftBalance);
    TNodeImp& child = LeftNode();
    PRECONDITION (child.balance == RightBalance);
    TNodeImp& grandchild = child.RightNode();
    child.right = grandchild.left;
    grandchild.left = &child;
    left = grandchild.right;
    grandchild.right = this;
    head = &grandchild;
    balance = child.balance = Balanced;
    if (grandchild.balance == RightBalance)
        child.balance = LeftBalance;
    else if (grandchild.balance == LeftBalance)
        balance = RightBalance;
    grandchild.balance = Balanced;
}

template <class Alloc>
void TNodeImp<Alloc>::RotateRightLeft (
    TNodeImp*& head)
{
    PRECONDITION (balance == DoubleRightBalance);
    TNodeImp& child = RightNode();
    PRECONDITION (child.balance == LeftBalance);
    TNodeImp& grandchild = child.LeftNode();
    child.left = grandchild.right;
    grandchild.right = &child;
    right = grandchild.left;
    grandchild.left = this;
    head = &grandchild;
    balance = child.balance = Balanced;
    if (grandchild.balance == LeftBalance)
        child.balance = RightBalance;
    else if (grandchild.balance == RightBalance)
        balance = LeftBalance;
    grandchild.balance = Balanced;
}

template <class Alloc>
BOOL TNodeImp<Alloc>::Balance (
    TNodeImp*& head)
{
    if (balance == DoubleRightBalance)
    {
        if (RightNode().balance != LeftBalance)
            RotateLeft (head);
        else
            RotateRightLeft (head);
        return 1;
    }
    if (balance == DoubleLeftBalance)
    {
        if (LeftNode().balance != RightBalance)
            RotateRight (head);
        else
            RotateLeftRight (head);
        return 1;
    }
    return 0;
}

#if __DEBUG > 0
#if defined(_DEBUG_B_TREE_)
template <class Alloc>
unsigned TNodeImp<Alloc>::CheckNode (
    int& height)
{
    int leftHeight = 0;
    int rightHeight = 0;
    unsigned cnt = 0;

    if (left)
        cnt += LeftNode().CheckNode (leftHeight);

    if (right)
        cnt += RightNode().CheckNode (rightHeight);

    height = max (leftHeight, rightHeight) +1;
    CHECK (balance >= LeftBalance && balance <= RightBalance);
    CHECK (leftHeight + balance == rightHeight);
    return cnt +1;
}
#endif
#endif

/*
 * Template TDNode
 * Contains functionality to manage direct data
 */
template <class T, class Alloc> class TDNode : public TNodeImp <Alloc>
{
public:
    TDNode (void) : TNodeImp<Alloc> ()
        {
        }

    TDNode (const T& value) : TNodeImp<Alloc> (), t (value)
        {
        }

    const T& Data (void) const
        {
        return t;
        }

    T& Data (void)
        {
        return t;
        }

    const T* DataPtr (void) const
        {
        return &Data();
        }

    T* DataPtr (void)
        {
        return &Data();
        }

    int operator == (const TDNode& other) const
        {
        return t == other.t;
        }

    int operator < (const TDNode& other) const
        {
        return t < other.t;
        }

private:
    T t;

    const TDNode& operator = (const TDNode&);
    TDNode (const TDNode&);
};

/*
 * Template TINode
 * Contains functionality to manage indirect data
 */
template <class T, class Alloc> class TINode : public TNodeImp <Alloc>
{
public:
    TINode (void) : TNodeImp<Alloc> (), t (0)
        {
        }

    TINode (T* value) : TNodeImp<Alloc> (), t (value)
        {
        }

    const T* Data (void) const
        {
        return t;
        }

    T*& Data (void)
        {
        return t;
        }

    const T* DataPtr (void) const
        {
        return Data();
        }

    T* DataPtr (void)
        {
        return Data();
        }

    int operator == (const TINode& other) const
        {
        return *t == *other.t;
        }

    int operator < (const TINode& other) const
        {
        return *t < *other.t;
        }

private:
    T* t;

    const TINode& operator = (const TINode&);
    TINode (const TINode&);
};
#endif